package com.hanxiaozhang.no3algorithm;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 〈一句话功能简述〉<br>
 * 〈例题1〉
 * java 无序数组中，找出两个元素相加等于N的所有组合？ o（n）
 *
 * @author hanxinghua
 * @create 2020/4/10
 * @since 1.0.0
 */
public class No1Example {

    public static void main(String[] args) {
        //初始化数组
        int[] table = {1, 38, 13, 33, 43, 47, 16, 44, 32, 10};
        int[] table1 = {12, 3, 5, 88, 19, 47, 16, 44, 32, 10, 34, 65, 99, 88, 12, 50};

        //方式1
        method1(table, 76);
        System.out.println("---- ---- ---- ----");

        //方式2
//        method2(table1, 100);
//        System.out.println("---- ---- ---- ----");


        //方式3
        method3(table, 76);
        System.out.println("---- ---- ---- ----");

        //方式4
//        method4(table1, 100);

    }

    /**
     * 最笨的方法：时间复杂度是o（n2）
     * 思路：第一循环找出第一个数；第二循环找出来第二个数，
     * 如果"第一个数+第二个数=N" 输出结果
     *
     * @param table
     * @param n
     */
    private static void method1(int[] table, int n) {
        int size = table.length;
        for (int i = 0; i < size; i++) {
            int temp = table[i];
            //注意：int j = i，不是int j = 0（有重复）
            for (int j = i; j < size; j++) {
                if (n == (temp + table[j]) && i != j) {
                    System.out.println(n + " = " + temp + " + " + table[j]);
                }
            }
        }
    }


    /**
     * 简单的方法：（理想情况下（无hash碰撞）可以：使用有限）
     * 思路：声明一个数组，使用hash原理（元素的值%数组长度=元素的在数组中位置）存储各元素是否存在的标志，
     * 即0：无，1：有。然后遍历数组，判断N与当前数组元素的差值在数组中是否存在,存在证明有该数。
     * 解析：该算法不要求数组有序，但要求一个hash数组的额外空间，时间复杂度是O(n)，
     * 并且要求元素去重后hash的没有碰撞(这个元素有两类：一是第一个数，即所有元素在新定义的数组中不会发生碰撞；
     * 二是（N-第一个数）的未知数，这个未知数在新定义的数组中不会发生碰撞)
     * 如何保证元素去重后hash无碰撞？合理设置数组的长度，长度是无序数组所有元素+N数中最大的值
     *
     * @param table
     * @param n
     */
    private static void method2(int[] table, int n) {
        System.out.println(Arrays.toString(table));
        //数组的长度
        int tableSize = table.length;
        //hash数组的长度，必须大于最大值
        int hashSize = 100;
        //声明一个hash数组
        int[] hash = new int[hashSize];
        for (int i = 0; i < tableSize; i++) {
            //hash表存储数组各元素是否存在的标志
            hash[table[i] % hashSize] = 1;
        }
        System.out.println("hash数组:" + Arrays.toString(hash));

        for (int i = 0; i < tableSize; i++) {
            int sub = n - table[i];
            // hash[sub%hashSize] == 1 -> sub哈希后的值存在 &&
            // sub >= table[i] -> 数组元素不重复，此条件可以避免出现数字颠倒的情况，例如： 100 = 88 + 12  100 = 12 + 88
            // sub%hashSize!=table[i]%hashSize -> 数组元素不重复，避免出现，同一个位置运算相加等目标值的情况，例如：100 = 50 + 50
            if ((hash[sub % hashSize] == 1) && (sub >= table[i]) && (sub % hashSize != table[i] % hashSize)) {
                System.out.println(n + " = " + table[i] + " + " + sub);
            }
        }
    }


    /**
     * 无序不重复数组中，寻找两个值等于目标值
     *
     * @param table
     * @param n
     */
    private static void method3(int[] table, int n) {
        Map<Integer, Integer> map = new HashMap<>(16);
        // 存储map中
        for (int i = 0; i < table.length; i++) {
            map.put(table[i], 1);
        }
        // 遍历map
        map.forEach((k, v) -> {
            // 差值
            int sub = n - k;
            // map包含差值；避免用一个元素相加；避免相同结果出现两次
            if (map.containsKey(sub) && sub + sub != n && sub < k) {
                System.out.println(n + " = " + k + " + " + sub);
            }
        });
    }


    /**
     * 支持重复元素。
     *
     * @param table
     * @param n
     */
    private static void method4(int[] table, int n) {
        // key：数值，value：数值对应的个数
        Map<Integer, Integer> map = new HashMap<>(16);
        // 存储数据
        for (int i = 0; i < table.length; i++) {
            int temp = table[i];
            int count = 0;
            if (map.containsKey(table[i])) {
                count = map.get(temp);
            }
            map.put(temp, count + 1);
        }

        // 变量map
        map.forEach((key, value) -> {
            // 差值
            int sub = n - key;
            // 处理重复元素
            for (int i = 0; i < map.get(key); i++) {
                // 存在差值元素，并且可用次数大于0
                if (map.containsKey(sub) && map.get(sub) > 0) {
                    // 去除key与temp值相同，但是数组中只有一个值得情况
                    if (!(n == sub + sub && map.get(sub) == 1)) {
                        System.out.println(n + " = " + key + " + " + sub);
                        map.put(sub, map.get(sub) - 1);
                        map.put(key, map.get(key) - 1);
                    }
                }
            }
        });
    }


}

